package com.ddshuai.tree.binarysearch;

import java.util.Objects;

/**
 * 描述 二叉搜索树 操作
 *
 * @author ddshuai
 * @date 2019-04-19 10:12
 **/
public class TreeNodeOperation {

    private static final TreeNode ROOT = new TreeNode(100);

    /**
     * 二叉搜索树特征，左子树数据要比右子树小
     *
     * @param child
     * @return
     */
    public static boolean insert(TreeNode child) {
        if (Objects.nonNull(child)) {
            TreeNode current = ROOT;
            while (true) {
                if (child.data > current.data) {
                    if (current.right == null) {
                        current.right = child;
                        return true;
                    } else {
                        current = current.right;
                    }
                } else {
                    if (current.left == null) {
                        current.left = child;
                        return true;
                    } else {
                        current = current.left;
                    }
                }
            }
        }

        return false;
    }

    public static TreeNode find(int data) {
        TreeNode current = ROOT;
        while (current != null) {
            if (current.data == data) {
                return current;
            } else if (current.data > data) {
                current = current.left;
            } else {
                current = current.right;
            }
        }

        return null;
    }

    public static void main(String[] args) {
        insert(new TreeNode(2));
        insert(new TreeNode(5));
        insert(new TreeNode(3));
        insert(new TreeNode(4));
        insert(new TreeNode(101));
        insert(new TreeNode(103));
        insert(new TreeNode(102));
        insert(new TreeNode(104));
        System.out.println(find(7));
    }
}
